

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

struct ListNode
{
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class CQueue
{
public:
    CQueue()
    {}

    void appendTail(int value)
    {
        _q.push(value);
    }

    int deleteHead()
    {
        if (_q.empty())
            return -1;

        int res = _q.front();
        _q.pop();

        return res;
    }
private:
    queue<int> _q;
};

class Solution
{
public:
    vector<vector<int>> zigzagLevelOrder1(TreeNode* root)
    {
        if (nullptr == root)
            return {};

        int level = 1;
        queue<TreeNode*> q;
        vector<vector<int>> res;

        for (q.push(root); q.size(); ++level)
        {
            vector<int> lev;

            if (level % 2)
            {
                op(q, lev, q.size());
            }
            else
            {
                vector<int> tmp;

                op(q, tmp, q.size());
                lev = vector<int>{ tmp.rbegin(), tmp.rend() };
            }
            res.push_back(lev);
        }

        return res;
    }

    vector<vector<int>> zigzagLevelOrder2(TreeNode* root)
    {
        if (nullptr == root)
            return {};

        int level = 1;
        queue<TreeNode*> q;
        vector<vector<int>> res;

        for (q.push(root); q.size(); ++level)
        {
            vector<int> lev;

            for (int i = 0, n = q.size(); n--;)
            {
                TreeNode* front = q.front();
                lev.push_back(front->val);
                q.pop();

                if (front->left)
                    q.push(front->left);
                if (front->right)
                    q.push(front->right);
            }
            if (0 == level % 2)
                reverse(lev.begin(), lev.end());
            res.push_back(lev);
        }

        return res;
    }

    vector<vector<int>> zigzagLevelOrder3(TreeNode* root)
    {
        if (nullptr == root)
            return {};

        int level = 1;
        queue<TreeNode*> q;
        vector<vector<int>> res;

        for (q.push(root); q.size(); ++level)
        {
            deque<int> lev;

            for (int i = 0, n = q.size(); n--;)
            {
                TreeNode* front = q.front();
                q.pop();

                if (front->left)
                    q.push(front->left);
                if (front->right)
                    q.push(front->right);

                if (level % 2)
                    lev.push_back(front->val);
                else
                    lev.push_front(front->val);
            }
            res.push_back(vector<int> {lev.begin(), lev.end()});
        }

        return res;
    }

    ListNode* mergeTwoLists1(ListNode* list1, ListNode* list2)
    {
        if (nullptr == list1)
            return list2;
        if (nullptr == list2)
            return list1;

        if (list1->val < list2->val)
        {
            list1->next = mergeTwoLists1(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists1(list1, list2->next);
            return list2;
        }
    }

    ListNode* mergeTwoLists2(ListNode* list1, ListNode* list2)
    {
        ListNode dummy;
        ListNode* tail = &dummy;

        while (list1 && list2)
        {
            if (list1->val < list2->val)
            {
                tail->next = list1;
                list1 = list1->next;
            }
            else
            {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        if (list1)
            tail->next = list1;
        if (list2)
            tail->next = list2;

        return dummy.next;
    }

    ListNode* reverseList1(ListNode* head)
    {
        if (nullptr == head)
            return nullptr;
        if (nullptr == head->next)
            return head;

        ListNode* newhead = reverseList1(head->next);
        head->next->next = head;
        head->next = nullptr;

        return newhead;
    }

    ListNode* reverseList2(ListNode* head)
    {
        ListNode* cur = head, * prev = nullptr;

        for (ListNode* next = nullptr; cur; cur = next)
        {
            next = cur->next;
            cur->next = prev;
            prev = cur;
        }

        return prev;
    }

    ListNode* swapPairs1(ListNode* head)
    {
        ListNode dummy;
        dummy.next = head;
        ListNode* cur = head, * prev = &dummy;

        while (cur && cur->next)
        {
            ListNode* next = cur->next;
            ListNode* nnext = next->next;

            cur->next = nnext;
            next->next = cur;
            prev->next = next;
            prev = cur;
            cur = nnext;
        }

        return dummy.next;
    }

    double myPow(double x, int n)
    {
        return  n > 0 ? _myPow(x, n) : 1.0 / _myPow(x, -(long long)n);
    }

private:
    double _myPow(double x, long long n)
    {
        if (0 == n)
            return 1.0;

        double tmp = _myPow(x, n / 2);

        return n % 2 ? tmp * tmp * x : tmp * tmp;
    }

    void op(queue<TreeNode*>& q, vector<int>& v, int n)
    {
        while (n--)
        {
            TreeNode* front = q.front();
            v.push_back(front->val);
            q.pop();

            if (front->left)
                q.push(front->left);
            if (front->right)
                q.push(front->right);
        }
    }
};

void Test1()
{
    ULLONG_MAX;
    cout << pow(2, 1500) - 1 << endl;
    cout << ULLONG_MAX << endl;
    cout << UINT_MAX << endl;
}

int main()
{
    Test1();
	
	return 0;
}